//TODO: Comentarios!
#include "contenedor.h"


#define DEBUG(x) if(x)
#define SETCONTORNO 0
#define BOTTOMLEFT 0
#define MAXLEFT 0
#define TRAZA 0
#define CALCALTURA 0
#define LISTADO 0
#define VACIOS 0

using namespace std;

   /** Constructor por defecto */
   Contenedor::Contenedor() {
      W = 0;
      H = 0;
      solucion = list<Rectangulo>();
   }
   /** Constructor
   * @param Altura y Anchura del contenedor */

   Contenedor::Contenedor( int w) {
      W = w;
      H = 0;
      /* Creamos el primer tramo del contorno */
      tramo tr;
      tr.i = 0;
      tr.f = getUltimaPos();
      tr.h = 0;
      contorno.push_front(tr);

   }


	/**
	 * Añade un rectangulo haciendo el bottomleft
	 * @param r Rectangulo a introducir
	 * */
   void Contenedor::addRectangulo(Rectangulo r) {
      int pos = 0;
      int h = 0;
      bottomLeft(r,pos,h);
      setContorno(pos,pos+r.getw(),h+r.geth());
   }

	/**
	 * Añade un Rectangulo en la posición y altura especificadas sin hacer bottom left
	 * @param r Rectangulo a introducir
	 * @param pos_inicio posicion (contada desde 0)dónde introducir el Rectangulo
	 * @param h_inicio altura a la que colocar el Rectangulo, debería ser la altura del tramo donde se situará
	 * */
	void Contenedor::addRectangulo(Rectangulo r, int pos_inicio, int h_inicio) {
		setContorno(pos_inicio, pos_inicio+r.getw(), h_inicio+r.geth());
	}
		
   /** Devuelve el ancho del contenedor
    * @return ancho de contenedor
    * */
   int Contenedor::getW() {
     return W;
   }

   /** Devuelve la última posición del contenedor, por lo general W-1
    * @return última posicion del contenedor
    * */
   int Contenedor::getUltimaPos() {
     return W;
   }

   /** Devuelve el alo del contenedor
    * @return alto actual del contenedor
    * */
   int Contenedor::getH() {
     return H;
   }

   /** Devuelve un int en función de si cabe el rectángulo o no
    * @param r Rectángulo que desea saber si cabe
    * @return 0 si no cabe. 1 si cabe tal cual está, sin rotar. -1 Si cabe rotandolo
    * TODO: No vale esta función
    * */
   int Contenedor::cabe(Rectangulo r) {
      if (r.getw() <= W) //Cabe sin girar
         return 1;
      if (r.geth() <= W) //Cabe girándolo
         return -1;
      else              //No cabe
         return 0;
   }


   /** Devuelve el alto maximo del contorno entre in y fin
    * @param ini inicio del bloque
    * @param fin fin del bloque
    * @return altura maxima
    * */
   int Contenedor::maxBottom(int ini, int fin) {
      list<tramo>::iterator it = contorno.begin();
      while ((it->f < ini+1) && (it != contorno.end())) { //Buscamos el primer tramo que nos afecta
         it++;
      }
      //if (it == contorno.end())
         //it--;
      int max = it->h;    //Asignamos altura
      while ((it->f < fin) && (it != contorno.end())) { //Comprobamos el resto de tramos que nos afectan
         it++;
         if((it != contorno.end()) && (it->h > max))
            max = it->h; //Actualizamos altura max si necesario
      }
      return max;
   }

    /** Devuelve el "left" maximo del contorno entre in y fin
    * @param ini inicio del bloque
    * @param fin fin del bloque
    * @return izquierda maxima
    * */
   int Contenedor::maxLeft(int h, int ini) {
      list<tramo>::iterator it = contorno.begin();
      if (contorno.size() == 1)
		return it->i;
      while (it->f < ini)
		it++;

      while((it->h <= h) && (it != contorno.begin())) {//Mientras podamos movernos a la izquierda
         it--;
         if ((it->h <= h) && (it->i == 0)) { //Pero si llegamos al cero sin problemas lo retornamos
           return (it->i);
        }
      }
      if (it == contorno.begin()){
         if (it->f <= ini) {
            return it->f;
         } else {
            return it->i;
         }
      }
       return (it->f); //Retornamos el limite
   }

   /** Coloca el rectangulo siguiendo el orden bottomLeft
    * @param rect rectangulo a colocar
    * */
   void Contenedor::bottomLeft(Rectangulo rect, int &pos_in, int &h_in) {
      int ancho = rect.getw();
      int h_anterior = INT_MAX; 
      int pos_anterior = INT_MAX;
      int h = 0;
      h = maxBottom(getUltimaPos()-ancho, getUltimaPos()); //Buscamos altura
      int pos = 0;
      pos = maxLeft(h,getUltimaPos()-ancho);               //Desplazamos a la izquierda
      while ((h_anterior != h) && ((pos_anterior != pos))) {// && (pos != 0))) {    //Repetimos hasta que ya no se mueva más
         h_anterior = h;
         pos_anterior = pos;
         h = maxBottom(pos,pos+ancho);
         pos = maxLeft(h,pos);
      }
      pos_in = pos;
      h_in = h;
   }

	/** Devuelve el hueco mínimo del contorno 
	 * @return struct tramo con el hueco mínimo
	 * */
	 
	 Contenedor::tramo Contenedor::getHuecoMinimo() {
		 list<tramo>::iterator it = contorno.begin();
		 tramo min = *it;
		 while(it != contorno.end()) {
			 it++;
			 if ((it->f - it->i) < (min.f - min.i))
				min = *it;
		}
		return min;
	}
			

   /** Actualiza el contorno añadiendo o modificando los tramos necesarios
    * @param ini: inicio del tramo
    * @param fin: fin del tramo
    * @param h  : altura a la que quedará el tramo. Hay que pasarle la suma del tramo actual más la del rectángulo
    * TODO : creo que están todos los casos posibles al añadir un nuevo rectángulo
    *          teniendo en cuenta que solo se permite bottom-left, por lo que el
    *          inicio de un nuevo tramo siempre será el inicio/final de otro.
    *          Comprobadlo a ver si falta algo    *
    * */
   void Contenedor::setContorno(int ini, int fin, int h) {
		if((ini < 0) || (fin > getUltimaPos())) {
			return;
		}
      list<tramo>::iterator it;
      it = contorno.begin();
      while ((it->i != ini) && (it->i < ini) && (it != contorno.end()))
         it++; //Aquí es donde insertaremos el nuevo
      
      list<tramo>::iterator ant = it;
      list<tramo>::iterator post = it;
      
      //Anterior a misma altura
      ant--;
      if ((it != contorno.begin()) && (ant->h == h)) {
         ant->f = fin;      
         while ((it->f <= fin) && (it != contorno.end())){
            it = contorno.erase(it);
         }
         if (it != contorno.end()){
            if (it->h == h)  {
               ant->f = it->f;
               contorno.erase(it);
            } else {
               it->i = fin;
            }
         }         
         setH(h);
         return;
      }
      
         
      //Caso 2: Posterior a la misma altura
         post++;
         if ((post != contorno.end()) && (post->h == h)) {
            ant = it;
            ant--;

               post->i = ini;
               contorno.erase(it);

            setH(h);
            return;
         }
          
      //Modificamos la altura de uno ya existente
      if ((it->i == ini) && (it->f == fin)) {    
         it->h = h;
         setH(h);
         return;
      }
          
      //Añadimos tramo nuevo
      tramo tr;
      tr.i = ini;
      tr.f = fin;
      tr.h = h;
      it->i = fin;
      
      ant = contorno.insert(it, tr);
      
      it = ant;
      it++;
      while ((it->f <= fin) && (it != contorno.end())) {
         contorno.erase(it);
         it = ant;
         it++;
      }
      if (it != contorno.end())
         it->i = fin;
      setH(h);

   }
   
   
   void Contenedor::listarContorno() {
	   list<tramo>::iterator it = contorno.begin();
      while(it != contorno.end()) {
         cout << "Inicio: " << it->i << " | Fin: " << it->f << " | Altura: " << it->h << endl;
         it++;
      }
      cout << "-------------" << endl<<endl;
  }
   

   /**
    * Actualiza la H si es mayor que la actual
    * */
   void Contenedor::setH(int h_) {

      if (h_ > H)
         H = h_;
   }

   int Contenedor::calcularAltura(list<Rectangulo> sol_in) {
      reiniciarContenedor();
      candidatos = sol_in;      
      list<Rectangulo>::iterator it = candidatos.begin();
      DEBUG(LISTADO) listarContorno();
      int size = candidatos.size();
      while (!candidatos.empty()) {
			solucion.push_back(*it);
         addRectangulo(*it);
			candidatos.erase(it);         

         int vacios = 1;
         it = candidatos.begin();
      }  
      //listarContorno();
      return H;
   }
   
   void Contenedor::reiniciarContenedor() {
      contorno.clear();
      H = 0;
      /* Creamos el primer tramo del contorno */
      tramo tr;
      tr.i = 0;
      tr.f = getUltimaPos();
      tr.h = 0;
      contorno.push_front(tr);
      //listarContorno();
      candidatos.clear();
      solucion.clear();
      imaginario.clear();
      
  }

   int Contenedor::calcularAreaVacia(list<Rectangulo> lista, int h) {
      int a = calcularArea(lista);
      int b = calcularArea(imaginario);
      int c = W*h;

      cout << "Área rectangulos: " << a << endl;
      
      return c-a;
   }
   
   int Contenedor::calcularArea(list<Rectangulo> lista) {
      list<Rectangulo>::iterator it = lista.begin();
      int area = 0;
      for (int i = 0; i < lista.size(); i++) {
         area += (it->getw() * it->geth());
         it++;
      }
      return area;
   }
